package leetcode.editor.cn;

public class _42_TrappingRainWater {
    public static void main(String[] args) {
        Solution solution = new _42_TrappingRainWater().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int trap(int[] height) {
            if (height.length == 0) {
                return 0;
            }
            int res = 0, n = height.length;
            int[] left = new int[n], right = new int[n];
            int l_max = height[0], r_max = height[n - 1];
            for (int i = 0; i < n; i++) {
                l_max = Math.max(l_max, height[i]);
                left[i] = l_max;
            }
            for (int i = n - 1; i >= 0; i--) {
                r_max = Math.max(r_max, height[i]);
                right[i] = r_max;
            }
            for (int i = 0; i < n; i++) {
                int rain = Math.min(left[i], right[i]) - height[i];
                res += rain;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}